#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<mpi.h>

typedef unsigned long long int  ullint;

ullint divisorValido(ullint n, ullint *r, ullint m){
	ullint i;
	for(i=0; i<m; i++){
		if(n%r[i]==0){	
			printf("part i: %llu ",i);
			return r[i];
		}
	}
	
	printf("ERRO divisorValido\n");
	
	return 0;
}

ullint geraDivisorPart(ullint n, ullint f, ullint i, ullint m, ullint raiz){
	
	ullint tamPart = (double) ceill(((double)raiz-(double)f)/(double)m);
	ullint inicio = f+tamPart*(--i);
	ullint fim = inicio + tamPart;
	ullint j;
	
	for(j=inicio; j<=fim; j+=j%2==0?1:2){

		if(n%j==0){	
			return j;			
		}	
	}

	return fim;
}

ullint geradordivisor(ullint n, ullint f, ullint m){
	
	MPI_Status status;

	ullint r[m+1];
	ullint i=0;
	ullint raiz=sqrt(n);
		
	for(i=1; i<=m; i++){
		MPI_Send(&n,1,MPI_UNSIGNED_LONG_LONG,i,123,MPI_COMM_WORLD);
		MPI_Send(&f,1,MPI_UNSIGNED_LONG_LONG,i,123,MPI_COMM_WORLD);
		MPI_Send(&i,1,MPI_UNSIGNED_LONG_LONG,i,123,MPI_COMM_WORLD);
		MPI_Send(&m,1,MPI_UNSIGNED_LONG_LONG,i,123,MPI_COMM_WORLD);
		MPI_Send(&raiz,1,MPI_UNSIGNED_LONG_LONG,i,123,MPI_COMM_WORLD);
	}
	
	for(i=1; i<=m; i++){
		ullint result = 0;
		MPI_Recv(&result,1,MPI_UNSIGNED_LONG_LONG,i,123,MPI_COMM_WORLD,&status);
		r[i-1] = result;
	}
		
	r[m]=n;
	
	return divisorValido(n,r,m+1);
}

void fatoracaoPrimos(ullint n, ullint f, ullint m){
	
	if(n==1){
		return;
	}
		
	ullint divisor = geradordivisor(n,f,m);
	printf("%llu \n",divisor);
	
	
	fatoracaoPrimos(n/divisor, divisor, m);
}

void execMaster(int argc, char **argv, ullint m){	
	
	ullint n = strtoull(argv[1],NULL,10);
	printf ("%llu \n", n);

	fatoracaoPrimos(n,2,m);
	
	printf ("\n");		
	
	ullint final = 0;
	int i;


	for(i=1;i<=m;i++){
		MPI_Send(&final,1,MPI_UNSIGNED_LONG_LONG,i,123,MPI_COMM_WORLD);
	}

	
}

void execSlave(int myid){
	
	ullint n = 0, f = 0, i = 0, m = 0, raiz = 0;
	ullint master = 0;
	ullint result;
		
	MPI_Status status;
		
			
	while(1){
		
		MPI_Recv(&n,1,MPI_UNSIGNED_LONG_LONG,master,123,MPI_COMM_WORLD,&status);
		
		if (n == 0){			
			break;
		}		
		
		MPI_Recv(&f,1,MPI_UNSIGNED_LONG_LONG,master,123,MPI_COMM_WORLD,&status);
		MPI_Recv(&i,1,MPI_UNSIGNED_LONG_LONG,master,123,MPI_COMM_WORLD,&status);
		MPI_Recv(&m,1,MPI_UNSIGNED_LONG_LONG,master,123,MPI_COMM_WORLD,&status);
		MPI_Recv(&raiz,1,MPI_UNSIGNED_LONG_LONG,master,123,MPI_COMM_WORLD,&status);
		
		result = geraDivisorPart(n,f,i,m,raiz);
		
		MPI_Send(&result,1,MPI_UNSIGNED_LONG_LONG,master,123,MPI_COMM_WORLD);
				
	}
	
}

int main(int argc, char **argv){
		
	int myid, numprocs, master = 0;
   
	MPI_Init(&argc,&argv);
    MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
    MPI_Comm_rank(MPI_COMM_WORLD,&myid);
	
		
	if(myid == master){
		execMaster(argc,argv,(ullint)numprocs-1);
	}else{
		execSlave(myid);
	}
	
	MPI_Finalize();
	
    return 0;
		
}
